perm filename PROPOS.AL[RDG,DBL] blob
sn#726119 filedate 1983-09-21 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00018 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 (Review) Proposal 11-Jan-82
C00010 00003 <revised form - never sent>
C00022 00004 <con't>
C00025 00005 <Overview of Thesis Proposal>
C00057 00006 Responses to Summary
C00060 00007 Etiology
C00061 00008 Rules
C00063 00009 Types of facts, used when describing an object
C00066 00010 Consider how analogies might be used by people wrt computer programs.
C00070 00011 ∂TO tw 12:01 14-Sept-82
C00073 00012 ∂22-Nov-82 2016 Russell Greiner <CSD.GREINER at SU-SCORE> Overview of Thesis Proposal
C00111 00013 < Where did this come from? It had been in ANALOG[rdg,dbl] >
C00116 00014 ∂16:08 2-May: lenat@score/su Sketch of Thesis Overview
C00123 00015 For MRG's ONL proposal: [Never used]
C00128 00016 ∂15-Sep-83 1800 greiner@Diablo Thesis overview
C00140 00017 ∂16-Sep-83 0644 BUCHANAN@SUMEX-AIM Re: Thesis overview
C00144 00018 ∂11:05 14-Sep: hart@sri-kl/su Events, past and future
C00155 ENDMK
C⊗;
(Review) Proposal 11-Jan-82
∂TO csd.lenat@score 17:41 11-Jan-82
What is this document?
I am currently searching (?floundering?) for a precise thesis topic,
rather that doing any "real" research.
The ideas now considered are very rough and preliminary -- most are
(at best) but first passes, needing much refining.
Hence, this description will NOT be
along the lines of Roget paper which Jim submitted;
not only would this be very difficult to produce,
but I can't imagine how such contorted answers would be useful.
In leiu of that,
below are a list of (hopefully) relevant questions and their answers.
Who am I?
Russell Greiner
5th year Grad student
What am I doing?
I am just beginning work on an application program
which will allow domain experts to use analogies when enterring
domain knowledge into a growing expert system.
Why is this is useful to HPP?
Most HPPer agree that knowledge acquisition is the current main problem facing
expert systems today.
Analogy is consider one strong method of solving this problem -- it would
allow the expert to communicate with the program in a natural manner; one
which saves him much of the drudgery of filling in "obvious" details.
What will the program (eventually) do?
Concocted scenario: An expert quickly teaches Mycin about a new class of
organism, X, by stating that X is just like streptococis, except that ...
The "analogizing" program now examing Mycin's KB of rules, and
proposes new rules to cover this X case, each generated from an existing rule, R,
using a proportional analogy
Streptococis:X :: R:<the new rule>.
Why am I doing this?
First, I believe a successful analogizing program will have a major impact
throughout AI.
The scenario shown above indicates how useful it is for building and
expanding an expert systems; mutatis mutandis it could be used in
other AI "learning" tasks as well.
I also feel this system may provide the groundwork for other analogy-related tasks:
using analogies to teach or explain a concept new to the student
(to TEACH about X, describe how it is similar to streptococis, ...),
and for predictions and conjectures
-- knowing that streptococis did this, expect X may do likewise
(or else that this X will have a similar effect - where the nature of the
similarity was determined from X's likeness to streptococis).
The second reason is more personal: I've fascinated by our human ability
to generate and understand analogies.
This seems a very fundamental and immensely powerful tool --
a capability which I believe any intelligent entity must have,
both to reason effectively and to communicate efficiently.
I'm excited at the prospect of working in this area.
How I intend to do it?
My research programme begins with a massive "knowledge acquisition" phase --
both from advisors and the available literature.
Finding input from the former sparse (though quite useful when transmitted),
I've spent the last month or two reading what I can find on analogy/metaphor,
from diverse fields - philosophy, psychology, AI (and here in learning and
more directly titled analogy papers).
In addition, I've been working through some dry-lab examples, and assembling
(and refining) a few proto-papers, including a thesis proposal to be.
How and where will the program fit into HPP?
Programs: Perhaps it will eventually be plugged into Eurisko; and/or written up
as a module which an MRS user can load in.
Personnel:
Perhaps TGD and/or MRG will need what this program provides for their respective
tasks. I feel a close collaboration would be profitable for me, and suspect
they might gain as well.
(We certainly should, in any case, avoid stepping on each other's toes.)
What do I need?
Better guidance -- I've found the faculty all but unapproachable. I will step
up my harrassment.
A few crisp, solid examples -- despite the HPP gospel quoted above, nobody
seems able to remember a single example of when they could have used a program
such as the one described above.
<revised form - never sent>
Description:
(What am I doing?)
This research effort is examining the role analogy can play in the
Knowledge Acquisition process.
The current focus is on an "analogy-understanding" module,
which allows a domain expert to define a new part of the domain
as being similar to some known part.
As a simple example,
consider teaching an immature (editor) expert system the various EMACS commands.
An obvious instruction would be
"word commands are just like character commands,
EXCEPT word commands use Meta rather than Control".
This analogy-understanding module will be responsible to updating the
knowledge base to include these new command,
as well as asking for any additional needed information.
Notice the (human) instructor is generating the analogy,
not this module.
There are two other types of tasks under consideration.
The first is teaching that editor Expert System a second editor --
this involves describing that second editor (say E) in terms of
the already known editor, say EMACS.
Again the module would be responsible (only) for using the editor-to-editor
analogies supplied by the expert,
not generating them.
A second, more ambitious task would use known facts, and observed analogies,
to generate new plausible connections.
This analogy-for-learning program might notice the C-x to M-x relation,
as manifest in the C-F/M-F, ... commands.
On seeing a C-T command,
it might guess a M-T command exists, and reason (correctly) it transposes words.
(Why this particular task?)
The topic "Analogy" encompasses a large number of diverse ideas.
If there is any coherent theme which permeates these different perspective,
it is that analogy is a (?the?) non-decomposition way of claiming that two
things are similar.
Understanding an analogy seems more basic a process than generating an analogy --
in that any generator must be able to verify that the analogy is (potentially)
apt. The setting of using a small, local analogy -- which permits a foreign
term to quickly "absorb" many (but not all, of course) of the details of a
familiar thing; seems the basic case of understanding an analogy.
(This is to be contrasted with the more general analogies,
which compare elaborate structures (e.g. electrical curcuits with water
flow systems. These larger systems seem composed of many smaller mappings,
systematically arranged.)
Within exegesis, there is still considerable breadth. I choose the KA task
because it is so readily verified -- the resultant expert system either uses
the newly acquired fact, or it doesn't.
(Yes, there is still the issue of cheating:
did it learn this new fact in a correct (ie general) way?)
Hence this particular research activity.
Motivation:
(Why do I think it will work?)
This research is based on the observation that it is much easier to teach
someone a second domain than it was to teach him the first;
especially when those two domain are similar.
Basically, that first domain (or part of the domain) will provide a
rough orgranization in which to store the new facts,
plus a host of familiar well-understood facts against which to match
the new terms.
This should be true for expert systems as well --
that incorporating additional facts should be faster and easier if
one already has a corpus of core facts, and a basic structure of
the domain.
(Why am I doing it?)
It is widely accepted that a (?the?) major problem in Expert Systems
is the Knowledge Acquisition bottleneck.
This programme is directly addressing this issue.
The tasks mentioned above show two ways
that analogy may be used by an expert system to acquire "expertise":
(1) by providing a natural language the domain expert can use
to efficiently and rapidly communicate pertanent facts,
and (2) by suggesting plausible new rules and facts, based on existing facts,
and prior analogical connections.
This analogizing capability seems most appropriate, and profitable,
for the final stage of Knowledge Acquisition (using JSB's three stages).
By this time a rough skeleton of the domain has been generated,
and many domain particulars have been enterred.
Fleshing out this structure requires many "Copy and Edit" steps.
At the very least this program should eliminate this tedious process --
or at least reduce the number of such modifications, and simplify that modifying
process.
(Why do I think it will work?)
While there are a number of analogizing programs, I know of no other
task
Research programme:
(How am I doing it?)
I am presently in a knowledge acquisition phase of this work --
trying to obtain the needed knowledge by a combination of reading,
writing and introspection.
(Following the learn by example approach I advocated above,)
I am generating a (dry-lab) scenario,
to demonstrate how this analogy-understanding program should behave.
This will be a living document -- which will be updated to reflect the
implementation (and my current thoughts) as necessary.
This emerging KA program will attempt to learn additional EMACS commands,
based on old ones.
While this task seems rather simple,
it has already forced me to examine a number of issues.
(Many are listed in the [Intellectual Difficulties] section.)
Eventually I would like to scale up to more complex (seeming) tasks mentioned
above, staying within the same editor domain
After that, I hope to address a less artificial, artifactual domain -- such as
molecular genetics or medical diagnosis.
(Note in both secondary tasks,
I am assuming that this initial body of "analogy" facts
(together with my preliminary organization of analogy,)
will provide both the framework I need to flesh-out
understanding of analogy, as well as an good starting set of potential analogues.)
For perspective on this task of analogy,
as well as to help me formulate my own ideas,
I am also working on a brief paper on "naive analogy".
This will record various thoughts on this topic -- both mine and others.
It will list many of the different senses of analogy found in the literature,
(based on task performed, as well as underlying theory,)
together with a set of "dimensions" used in these descriptions.
Tactics:
(How am I going about coding this up?)
<<Nothing yet>>
Milestones:
(Where am I, and when will I be where?)
While I am not ready to be tied to particular absolute times for the following,
below is my suggested relative completion dates.
Finish thesis proposal, including the desired scenario
Current status: Ok - needs to integrate the scenario
Finish writing, and circulate, a draft of NaiveAnalogy paper
Begin coding the KA system to handle this case
This will require writing a crude performance module, etc.
(This looks like a job for MRS! or maybe RLL? or EMYCIN?)
Intellectual difficulties:
(What questions am I just beginning to address?)
As mentioned above, there are several issues which arise, even in this simple
example, within this restricted application of analogy.
* Initial state of pupil
(not too literate, nor too ignorant)
* Pupil's rep'n important -- can make analogy trivial, or interesting
* Language for expressing "A is like B, except...."
* Alterring "known" facts - eg rearrange domain skeleton
There is also a major meta-level issue to be resolved:
How does one demonstrate that the expert system now knows a new fact, and
can use it appropriately?
The real issue is how to ask the question -- and whether the question
somehow encodes the desired answer.
(This is, of course, a general problem for learning systems in general.)
<con't>
I will be designing an interactive analogy-understanding module,
which will be used to expand a growing KB of domain facts.
That initial KB must be rather complete -- having many things
to use as vehicle. (But not so much that this use of an analogy is silly.)
We will say the system "understands" the analogy when it can use the
topic appropriately.
(E.g. the system "understands" the M-F command when it uses this command
whenever it wants to move forward a word, and only in such situations.)
-----
Position in Analogy-Space
(See "What's in an Analogy" paper.)
Similarity metaphors (or proportional -- but NOT familial)
Use of the analogy, NOT its generation.
Deductive -- when only a conjecture, it will be examined interactively.
Linguistic (not rep'n)
Pretty much at Instance level --
o specificity can vary, but usually at the most precise level
o it will end up applying to new single commands, rather than
classes of commands
(although they may be communicated in that more generic manner)
Cases will be "closed" -- well definnd single use, and then discardable
Obvious
Refined
IntRAfield -- only from other things pertanent to editors...
Interactive
-----
Given input of the form "X is like Y because α",
this system will basically do a SOPHISTICATED copy and edit:
The smarts will come from deciding what to carry over, and how.
Hence the issues include
1) What features should be
transfered, guaranteed
transfered, with only a Y/N question
(where Yes is expected, and No requires other work)
transfered, with value only suggested
not even considered
2) the value of the feature may be
simply copied from vehicle
modified "guaranteed"
modified suggestively
restricted to a small set
<Overview of Thesis Proposal>
∂TO shortliffe@sumex, csd.lenat@score/cc, csd.genesereth@score 16:09 28-June-82
∂TO csd.dietterich@score/su (Copy of Proposal sent to Shortliffe) 14:41 2-Jul-82
∂TO darden@sumex/su Summary 12:38 12-Jul-82
∂TO schooley@rutgers 17:14 20-Jul-82
∂TO tw 11:46 14-Sept [with message on page 11]
<Overview of Thesis Proposal>
Terry -
This is a copy of the material I mailed to Ted Shortliffe recently;
it is serving as my most up to date thesis proposal.
My next message will outline particular places where I would especially
value your comments and insights.
Russ
------
I am currently investigating how analogy may be used to facilitate
Knowledge Acquisition. The goal is a module which will allow the domain
expert to state that a new domain object or set of objects are analogous
to some known object(s).
For example, it will permit a medical expert to use statements like
(*) "Viral-meningitis is like Bacterial-meningitis,
except it is caused by a virus."
to describe Viral Meningitis. From this, we (and hence any sophisticated
system) should be able to conjecture that this new item,
viral meningitis,
is a disease,
which is caused by a virus,
has symptoms which closely resemble those of bacterial meningitis,
(perhaps even specifying in what ways they are alike and different)
but whose etiology is totally different,
and whose treatment should be quite distinct.
This summary will walk through this simple example, to illustrate the type
of operations this analogizing module must be able to perform, and where
research time and effort must be channeled. The next subsections will
sketch how the analogizer will be able to reach these conclusions,
first outlining the analogizing process itself, and then instantiating
these steps using this example. We will next expand and "correct" many of
the simplifications found in this quick first pass. It will be clear that
the analogizing program must have access to a great many different types
of facts; many of these are enumerated in the next part. We next discuss
the benefits stemming from both this module itself, and from this line of
research. The concluding remarks indicate where the work is now, and
what some future directions might be. This is followed by an appendix
which discusses reformulation.
<<Meta note: please forgive the technical inaccuracies filling this short
synopsis. The goal is to present an idea of what the analogizer should be
able to do, not to differentiate different forms of meningitis.>>
! ---Overview of Analogizing Process---
For this example to work, the existant MedicalKB must already know a lot
about bacterial meningitis. In particular, it must know that bacterial
meningitis is a certain kind of disease, with a particular etiology, set
of symptoms and treatments. Our goal is to derive facts and conjectures
about viral meningitis, based on those bacterial meningitis assertions.
(Stated another way, we are creating a new unit for Viral-meningitis by
"Copy and Edit"ing the Bacterial-meningitis unit. This involves
discerning which of the Bacterial-meningitis slots are appropriate for
this neo-natal Viral-meningitis unit; and then what values should fill
these slots. One might, for example,
(i) simply copy the value, as it stands;
(ii) perform a simple lexical substitution first;
(iii) perform some elaborate "mutatis mutandis" modification, based
directly on some first principles of the fields, etc.)
The basic procedure is an incremental "generate and test". Various
"suggestive" heuristics will propose hypotheses about this
Viral-meningitis. Other rules will then examine these proposals, pruning
those which are contradictory (or just very unlikely). Those conjectures
which are accepted are recorded, together with a body of reinforcing (and
negating) justifications. This propose-and-verify-cycle will continue
until no more generating rules are triggered.
Three quick points:
1. This overall process will be user-interactive. That is, any rule may
call upon the user to answer some question which is outside the expertise
of the analogizer or the current MedicalKB.
2. A rule may declare that some earlier assertion is faulty, and cause it,
and all of its effects, to be thrown out. This will require some form of
Reason Maintenance System, a la [Doyle].)
3. While most users will probably simply use the rules supplied,
he does have the option of modifying them to conform to his desired sense
of analogy.
! ---Example Itself---
Enough overhead; onto the actual conjectures. How did we know that
Viral-meningitis is a disease? (Realize that stating that
"This sponge is like meningitis,
in that both have an excess storage of fluid."
does not imply that "this sponge" is a disease.) Of course we still don't
really know that this is true. It is a quite plausible conjecture,
though, as we do know that viruses cause diseases, and (*) stated that
Viral-meningitis was caused by a virus. Such "converse" statements are
viewed as reinforcements of some idea, not as proofs. (E.g., a virus can
cause a contamination of an otherwise pure culture, or ...)
But why did we even consider asking whether Viral-menigitus was a disease?
This was done at the behest of the general analogizing heuristic:
IF the user asserts that "X is like Y",
THEN consider setting X:IsA to the same value as Y:IsA.
That is, we will see if this conjecture,
(regarding the classes to which Viral Meningitis belongs,)
is consistent with other facts and conjectures about this new concept.
(Two digressions:
1. One of the most powerful arguments "justifying" this heuristic is that
this IsA classification is often based on the obvious perceived
similarities, on which most analogies are also based.
2. Many other analogizing system insist that the analogues both belong to
the same class -- i.e. share a common IsA value. We will show later (in
Reformulation part) why this is a serious limitation, and how this system
avoids this constraint.
...but now back to the plot...)
Having established that these two analogues are both diseases, we next
consider what it means for two diseases to be considered similar. A
medical-domain-specific heuristic states that two diseases are similar if
they manifest similar symptoms, and possibly have similar causes. Finding
that the name "Viral-menigitus" is similar to "Bacterial-menigitus"
reinforces the conjecture that they should share similar symptoms.
(Afterall, these two diseases may have been named long before anyone
understood the organisms responsible.) [This "similar name check"
heuristic is also specific to this medical domain.] As we've been told
their respective causes are different, we know to rule out the "similar
causes" conjecture.@FOOT<Of course another MD might only consider two
diseases to be similar if they are caused by the same organism. Such an
expert would be able to enter and use this rule, in leiu of the "similar
diseases have similar symptoms" heuristic discussed above. Of course
this would mean this KA module would have a harder time understanding
this particular (*) analogy.)
Are the two sets of symptoms actually identical? Maybe -- realize we do
not have enough information to determine this yet. We can, however,
simply ask the nearby domain expert.
@FOOT<This question itself might be ill-formed, as we are really comparing
two CLASSes of diseases, not two single diseases. It is quite possible
that one member of each class will share identical symptoms, while other
members of each class will not have such correspondents.>
The fact given in the initial analogy, (*), that these two diseases have
different causes means that their respective etiologies will be
different -- although the similarity of the symptoms places some
constraints on how diverse the etiologies can be. The ontogeny of the
different organisms, likewise, must satisfy some connecting constraints.
[This reasoning will be based on several things. It requires, first, a
basic understanding of some medical "first principles"; here, of the
distinction between bacteria and viruses. In addition, the relation of
cause to etiology must be known, etc.]
Finally, the desired treatments may be completely different -- clearly
antibiotics (which may have some effect on the first bacterial disease)
will be useless for the second viral form. [This again derives from a
combination of general facts about etiology -- that different causes imply
different end results -- and from basic knowledge of bacteria and
viruses.]
! ---Other Points---
End of the scenario-overview. There are still many second-order issues
which were glossed over, which must be resolved before this process can be
implemented. All of the operations mentioned dealt with slots -- either
determining that a given slot was relevant for a particular unit, or
finding a value for a slot. This is a simplification in two ways. First,
we will really be concerned with general N-ary relations, rather than the
intrinsically binary slots. Second, there will be other operations which
will only place a restriction on the arguments of a proposition, but still
not fully specify these values. (E.g. we may insist that the value of x
in (IsA Analogue2 x) be a member of some set, or that it NOT be some
value, etc.) It is still safe to say that each operation of the
analogizer will attempt to more completely specify some fact about the new
analogue.
The next point deals with the order of those operations -- which
conjectures to propose first, and which later. How, for example, did we
know to first determine Viral-meningitis:IsA? The answer is common sense,
encoded as rule-ordering heuristics. (The "Do IsA first" heuristic is
easy to justify: this "is a particular kind of" relation provides a good
discriminant for subsequent facts; the conjectured value to use is easy to
compute -- i.e. it is usually the same as the IsA of the other analogue;
etc.)
The third "nuance" is a major issue, one which seperates this research
from that of other analogy programs: this program will be able to
"reformulate" the vehicle
@FOOT<This vehicle/topic/ground terminology comes from [Paivio].>
if necessary; and then use THESE newly generated
features for the analogy -- that is, the analogizer will map these
features over to the other analogue. In these cases, the analogizer will
first find a different description of the first analogue, one in which its
relation to the new concept is more apparent. A concluding appendix will
better define this term "reformulation", and provide some examples
justifying why it is needed.
! ---Prerequisite KBs---
As we saw throughout the example above, a lot of knowledge, about various
things, is required to reach these obvious conclusions. We had to employ
facts particular to this medical domain, (including pharmacological facts,
knowledge of infections in general, [e.g. diseases are considered similar
if they exhibit the same "behaviour" (reinforced by naming convention)],)
as well as facts about analogies in general, observations about salience,
etc.. In addition, we needed to include many "common sense" notions --
including a general understanding of causality (e.g. Treatment should be
related to Cause); and a variety of general heuristics -- including the
"Copy IsA, whenever possible, as soon as possible" rule. How to encode
these diverse facts is a major research challenge.
! ---Usefulness---
There are several strong justifications for this work. It will contribute
both to Expert System technology in particular, and to AI in general.
Reasons (1) and (2) below indicate why we feel that this elaborate
automated "copy and edit" process, in and of itself, will facilitate the
construction of superior KBs, faster. (These claims are, of course,
currently just conjectures. They will be empirically tested when this
module is up and running.) This is, however, only the "straight-forward"
component of the a more exciting program(me). Reason (3) discusses our
use of reformulation, which we feel is a contribution to AI in general.
(1) The resultant KB will be more accurate.
By automating much of the KA process, the domain expert is spared the
arduous and exacting task of actually inputting each specific fact about
each new object. Not only will this module help when fleshing out
skeletons during the 2nd KA stage, (see [Bennett: Sacon],) it could also provide
a Tieresias-like ([Davis]) verification, to insure that like objects have similar
features, with similar values. (Here the check can exceed Tieresias's
purely syntactic check, using some of its domain knowledge to determine,
for example, just how the values of a given slot for two different units
should compare...) [Actually, this verification would be a (hopefully)
straightforward embellishment to the proposed module.]
(2) The KB will be generated and refined faster.
This is because the language used for the interaction is more accomodating:
a) It is more natural to the expert.
Pf: Consider how experts communicate amongst themselves -- "this patient
just like that one", or "these chemicals are just like those", or "think
of this as water flow", ...
b) It is more succinct -- relatively few symbols will be used to encode many
assertions.
Pf: Claiming "A is like B" really "expands" into a host of assignments of
facts about A. (Of course storing the declarations which are used to
translate from the statement of the analogy to those assignments may be
non-trivial.)
(3) This module will be able to reformulate the analogues as a first step
in finding the relevant analogy. This may involve simply high-lighting
one particular perspective (or feature-space) of the vechicle, or the more
complex task of deriving a new space of features. (The appendix will
explain this use of reformulation -- telling what we mean by this term,
and why we consider it essential.)
! ---Related (dare I say analogous?) future work---
The ability to comprehend a given analogy, even in these rather
constrained situations, seems a prerequisite for many of the other uses of
analogy. Given a module capable of this behaviour, one could imagine
using it to use intERfield connections -- e.g.
"A text editor is like a Secretary, except ...", or
"Computer diagnosis resembles Human diagnosis in that ...",
etc.
The task of finding the best analogue (that is, finding the case which
most resembles some current situation,) would surely use the capability
of understanding how two particular situations are similar, which is just
what this proposed module would provide. (The expert who works from cases,
who examines his 50 - 100K friends (see [Simon]), searching for the one
which is closest to his current case, is using just this ability.)
Consider how one might use analogy for teaching: One has to find to find
the desired analogue-pairs to present, (which is basically the "find best
analogue" task described above,) together with a description of how they
are (and are not) related, which is closely related the KA task discussed
here. The flip-side of teaching, learning, is precisely the KA task.
! ---Conclusion---
This sketch hints at the numerous advantages of using analogy during
Knowledge Acquisition. To make this point (and my thesis) more concrete,
I clearly need is a body of real examples. Trying to be my own Domain
Expert, I originally chose the (more familiar to me) domain of editor
commands as principle domain. This has the major drawback that it is
sufficiently artificial and artifactual that any derived intrafield
analogy felt both obvious and un-interesting.
This is why I would like to "connect up" with you: [Ted Shortliffe]
to get one or more realistic KA scenarios, each one reflecting a real
(hopefully medical) situation, (which, who knows, may even help the domain
expert it was designed to benefit...) This is what I would like to discuss with
you, at your convenience.
*********
! ---Appendix: More on Reformulation---
Unlike other analogizing programs, this system does NOT depend on one
particular representation for the analogues. It can, instead, select the
most apt perspective, or even generate a new feature space if necessary.
The features the topic will "inherit" will be from that feature-set.
This appendix will answer the questions: Is this reformulation step useful?
If so, why have prior analogizing programs been able to use a single
representation, seemingly able to completely avoid this problem?
One very seductive property of analogies is that any given analogy is
obvious, in retrospect. Once one has described how the analogues A and B
are similar (in general because they are both Ys) any feature which you
find both A and B share will seem obvious -- of course P(x) holds for both A
and B; it holds for all members of Y!
Unfortunately, one does NOT always start with this crisp Y class; instead,
one may be forced to infer it from the examples. This is one of the real
challenges of this work (and its major AI contribution) -- determining how
to glean from the vehicle, together with a brief description of the
desired analogy, the space of relevant facts to map from this analogue
over to the topic.
We need a different example to demonstrate the usefulness of this
reformulation step. Consider first the obvious connection between blood
and lymph -- as each IsA circulating bodily fluid, it is not surprising to
find many correlations. Now imagine that someone said that the endocrine
network is similar to the blood system, except it uses "message carrying"
hormones rather than indistinguishable mass-type blood.
This endocrine system is clearly NOT a circulating bodily fluid. It does,
however, share many properties with such systems. For example, a pathway
may be blocked, preventing transference of the material. Or there maybe
some feedback loops. And, given such a topology, there are a host of
problems which might arise. (E.g. some "Stop Sending" signal might be
lost if the return part of the feedback loop was either open or blocked.)
The reason for these commonalities should be apparent: in both cases some
material is travelling from one location to another. Hence any of the
properties associated with "material flow" should pertain to both of these
systems. But what if the current system lacks this essential category?
We would still want the analogizer to consider endocrine-related illnesses
which resemble blood-blockage, or open-loops. [Sorry I don't know the
names for these ailments.] After analyzing this situation, we may want
to reconfigure the KB to actually have a Material-Flow class, which is a
superset of "circulating bodily fluids", and the class to which "endocrine
system" belongs. Thenafter anything which IsA MaterialFlow would inherit
all of those facts common to such systems -- including this list of
possible illness causes.
(We might later consider connecting our Neurological Networks (or even
electrical curcuits in general) with that endocrine system. They are both
instances of elaborate circuits, and, as such, subject to certain classes
of disruptions.)
As mentioned above, it is only in aftersight that the need for such
categories became obvious -- it is silly to think that we might have
known this, and every other type of relevant category, beforehand.
Solving this challenge -- of how to find such commonalities when they
are needed, especially when they are NOT explicit in the representation,
but rather have to be teased out -- is a major reseach effort.
Responses to Summary
∂TO CSD.GENESERETH@SCORE 11AM 30-June
No, no, no
∂29-Jun-82 1652 <CSD.GENESERETH at SU-SCORE> Re: <Overview of Thesis Proposal>
I got your message. Seems like a lot of words.
mrg
You're totally misinterpreting it! When printed out, in the standard
Helvetica font, and held in front of a mirror, with the sun over your
left shoulder, it appears as a PICTURE of a Buddhist monk, meditating under
a zuchinni shrub, in a winter snow; OBVIOUSLY!
Sometimes I wonder about you, Mike...
∂30-Jun-82 2226 <Shortliffe at SUMEX-AIM> Re: <Overview of Thesis Proposal>
cc: csd.lenat at SU-SCORE, csd.genesereth at SU-SCORE
Russ,
Thanks for sending along a copy of your thesis proposal. Will look
it over and get back to you.
Regards,
Ted
Etiology
Different Causes require Different Treatments
Medical
Each disease has a
Etiology (causes), Sign/Symptoms, Treatment
[?other connections: pre-disposition, prevention, ...]
Similar diseases have similar symptoms
Different organisms require different treatments
Bacteria (but not viruses) can be killed by AntiBiotics
General
Copy IsA whenever possible
----
Meta
Determine IsA as soon as possible
Rules
<<Situation: Given "A is like B, for reason C", and lots is known about B,
fill in facts about A. >>
ToFind: A:Isa --
Set A:Isa ← B:Isa, and tag this experimental.
[perhaps using a different theory, CONSIDER]
Do Isa first
Similar diseases have similar symptoms
Similar causes lead to similar treatments
Use antibiotics to treat diseases caused by (certain) bacteria.
Diseases are caused by Disease-Agents.
Disease-Agents include Bacteria and Viruses
Meningitus is a class of diseases,
indicated by an inflamation of the meninges.
Two types of treatment:
(1) Address the symptoms -- e.g. lessen pain
(2) Address the causal agent -- e.g. knock up bacterial infection
---
Bacterial-Meningitis Isa Disease
Viral-Meningitis
Types of facts, used when describing an object
1) Purpose/role --
2) Functionality
I/O behaviour, (dynamic) states
Operations
3) Internals
Components, Material, Structure (interconnectednesses)
4) Classification
5) Other things -- ontogeny, history, effects, ...
-----
Instance: a filing cabinent
1) Purpose/role --
to house folders
(sometimes securely, usually organized, always partitioned)
2) Functionality
I/O behaviour: ?
dynamic states: cabinent may be locked; contents may be sorted;
it may be full; the i-th drawer may be open; it may be out of place; ...
Operations: Lock it, sort its contents, ... <at least one per state>
3) Internals
Components: Drawers, (vertically stacked,) folders, <contents of folder>
indices (one to a folder)
Material: Metal structure, paper folders, paper/plastic folder contents
Structure: Stacked Drawers, housed in a frame, is a filing cabinent.
Each drawer has a "list" of contents, partitioned into folders, ...
4) Classification
Isa Physical object, usually found in an office, often in groups,
"processed" by office-workers (secretaries, office clerical workers, ...)
--- Folders contain information, encoded in words on paper, ...
5) Other things
<concept of Filing cabinent>
Designed by ?, in 1???, for ??? , in the country ???, in exchange for $? There are ? in use today
<typical filing cabinent>
Average lifespan is ? years; during which time having ? owners
<set of filing cabinents>
There are now ? fc's in the world, ?% in the US, ??% in offices of ...
<specific filing cabinent>
"Did you hear the joke about the traveling FC who ..."
The Smithsonian houses ...
-- amusing/relevant anecdotes --
Pol-glycote finish caused cancer in teenage rodents, on Thursdays, ...
Consider how analogies might be used by people wrt computer programs.
(1) Analyze/understand program A, based on knowledge about B, and connection
of A to B.
(2) Generate new code, by analogy with existing code
(a) Create a new program
(b) Augment an existing program
(3) Modify existing code, in running/errorful program
[Note similar types of bugs, ... in different programs]
(4) Device a macro, capable...
--------
Scenarios:
o I know about MAPCAR, and am told EVERY is similar, but ...
Deduce what EVERY does.
o Given spec for EVERY, copy and edit MAPCAR to perform this function.
(or MAPC, or MAPLIST, ...)
o Concoct the macro which is used to implement these mapping functions
o Optimize code -- same I/O, but faster or less space (e.g. DMAPCAR)
o Given PR-STASH, generate PL-STASH, which works with Property lists,
rather than the hash table PR-STASH used.
o Figure how to write PL-UNSTASH,
given relation of PR-STASH to PR-UNSTASH, & PL-STASH.
o Given MACLISP code for function F, rewrite F in InterLisp.
or Pascal, or FORTRAN, SETL, APL, ...
o Change the data structure
-- e.g. deal with linked lists, not bit vectors
o Change the type of objects program X deals with
(not just their representation)
Given UNION, and def'n of SET and LIST,
write (various flavors of) APPEND
-------
Why this domain -- of programming?
* one has "complete" information --
hence if one representation doesn't work, can produce another one
(starting from that "primitive" code) -- `reformulation'
* perhaps will be used to concoct a new representation -- eg programs
which use certain tricks, or written by Fred (who likes capital
letters)
[is this exactly "learning by ostention"?]
-------
How can Program A be like Program B?
* wrt I/O behavior
o (abstract) functionality -- e.g. both "sort"
o Data structures involved -- eg linked list, not bit string
o "interpretation of data" -- eg sets vs lists
o Timing - both absolute CPU or real time, or assymptotic
* wrt structure
o procedure calling sequences -- eg CAR recursive, ...
o details of code -- eg variable names
Nuances of coding style of
Author, Author's school, ...
(e.g. DBL: Long variable names, many globalvars)
o Language used for implementation
o Abstract description of code
"tricks used" -- i.e. version space, or path compression
same task -- e.g. learning
∂TO tw 12:01 14-Sept-82
Specific Issues
Terry -
Below is a list of specific questions I have about this project,
which I would particularly like to discuss. I would, of course, value
any and all other comments/ suggestions/ proposals you could volunteer.
Thank you again for your time and energy; I look forward to meeting with
you at noon, 21/Sept,
Russ
-----
(1) General comments on this project:
Is this thesis-worthy and relevant?
Do you think it will be useful?
Is it doable? If not, on what subset should I concentrate?
...
(2) I never explicitly stated the model of analogy I was using:
I think of an analogy problem as a statement of the form
"A is like B within constaint C". (I even have a partial catalogue of such
constraint clauses.)
The "goal of the analogy" is to enhance/complete this description,
which is achieved by finding additional correspondents between A and B,
(thereby expanding this constraint C).
I'm very curious on your comments wrt this model;
e.g. its generality, or constraints, and issues of implementation.
That point leads to
(3) Linguistic aspects of this task,
in particular how to handle issues like context and initiative.
(... based on the observation that it is often possible to omit this
"within constraint C" clause; as it can be inferred from context...)
I have been totally ignoring these issues, viewing them as frills which can
be tacked on at the end. Do you think this view is wrong? Should I, instead,
be concentrating on these issues? Are they really part-and-parcel of this
analogy task?
...
∂22-Nov-82 2016 Russell Greiner <CSD.GREINER at SU-SCORE> Overview of Thesis Proposal
To: dekleer at PARC-MAXC
cc: rdg at SU-AI
Dr deKleer -
This is a (only slightly modified) copy of the material I mailed to Ted
Shortliffe a while back; it is serving as my most up to date thesis proposal.
A few of the ideas are antediluviated [my favorite self-referential word];
we'll be able to discuss the differences tomorrow. The most relevant part
is the second appendix, which outlines the water system/electrical circuit
analogizing task. (Feel free to regard everything else as background, and
simply skim through it.)
Thanks for your help. See you tomorrow,
Russ
------
I am currently investigating how analogy may be used to facilitate
Knowledge Acquisition. The goal is a module which will allow the domain
expert to state that a new domain object or set of objects are analogous
to some known object(s).
As a simple example, it will permit a medical expert to use statements like
(*) "Viral-meningitis is like Bacterial-meningitis,
except it is caused by a virus."
to describe Viral Meningitis. From this, we (and hence any sophisticated
system) should be able to conjecture that this new item,
viral meningitis,
is a disease,
which is caused by a virus,
has symptoms and manifestations which closely resemble those of
bacterial meningitis,
(perhaps we can even specify in what ways they are alike and different)
but whose etiology is totally different,
and whose treatment should (therefore) be quite distinct.
This summary will walk through this simple example, to illustrate the type
of operations this analogizing module must be able to perform, and where
research time and effort must be channeled. The next subsections will
sketch how the analogizer will be able to reach these conclusions,
first outlining the analogizing process itself, and then instantiating
these steps using this example. We will next expand and "correct" many of
the simplifications found in this quick first pass. It will be clear that
the analogizing program must have access to a great many different types
of facts; many of these are enumerated in the next part. We next discuss
the benefits stemming from both this module itself, and from this line of
research. The concluding remarks indicate where the work is now, and
what some future directions might be. This is followed by a pair of
appendices which discuss reformulation, and then a quick sketch of a more
elaborate analogizing example.
<<Meta note: please forgive the technical inaccuracies filling this short
synopsis. The goal is to present an idea of what the analogizer should be
able to do, not to differentiate different forms of meningitis.>>
! ---Overview of Analogizing Process---
For this example to work, the existant MedicalKB must already know a lot
about bacterial meningitis. In particular, it must know that bacterial
meningitis is a certain kind of disease, with a particular etiology, set
of manisfestations, symptoms and treatments. Our goal is to derive facts
and conjectures about viral meningitis, based on those bacterial meningitis
assertions. (Stated another way, we are creating a new unit for Viral-
meningitis by "Copy and Edit"ing the Bacterial-meningitis unit. This involves
discerning which of the Bacterial-meningitis slots are appropriate for
this neo-natal Viral-meningitis unit; and then what values should fill
these slots. One might, for example,
(i) simply copy the value, as it stands;
(ii) perform a simple lexical substitution first;
(iii) perform some elaborate "mutatis mutandis" modification, based
directly on some first principles of the fields, etc.)
The basic procedure is an incremental "generate and test". Various
"suggestive" heuristics will propose hypotheses about this
Viral-meningitis. Other rules will then examine these proposals, pruning
those which are contradictory (or just very unlikely). Those conjectures
which are accepted are recorded, together with a body of reinforcing (and
negating) justifications. This propose-and-verify-cycle will continue
until no more generating rules are triggered.
Three quick points:
1. This overall process will be user-interactive. That is, any rule may
call upon the user to answer some question which is outside the expertise
of the analogizer or the current MedicalKB.
2. A rule may declare that some earlier assertion is faulty, and cause it,
and all of its effects, to be thrown out. This will require some form of
Reason Maintenance System, a la [Doyle].)
3. While most users will probably simply use the rules supplied,
he does have the option of modifying them to conform to his desired sense
of analogy.
! ---Example Itself---
Enough overhead; onto the actual conjectures. How did we know that
Viral-meningitis is a disease? (Realize that stating that
"This sponge is like meningitis,
in that both have an excess storage of fluid."
does not imply that "this sponge" is a disease.) Of course we still don't
really know that this is true. It is a quite plausible conjecture,
though, as we do know that viruses cause diseases, and (*) stated that
Viral-meningitis was caused by a virus. Such "converse" statements are
viewed as reinforcements of some idea, not as proofs. (E.g., a virus can
*cause* a contamination of an otherwise pure culture, or ...)
But why did we even consider asking whether Viral-menigitus was a disease?
This was done at the behest of the general analogizing heuristic:
IF the user asserts that "X is like Y",
THEN consider setting X:IsA to the same value as Y:IsA.
That is, we will see if this conjecture,
(regarding the classes to which Viral Meningitis belongs,)
is consistent with other facts and conjectures about this new concept.
(Two digressions:
1. One of the most powerful arguments "justifying" this heuristic is that
this IsA classification is often based on the obvious perceived
similarities, on which most analogies are also based.
2. Many other analogizing system insist that the analogues both belong to
the same class -- i.e. share a common IsA value. We will show later (in
Reformulation part) why this is a serious limitation, and how this system
avoids this constraint.
...but now back to the plot...)
Having established that these two analogues are both diseases, we next
consider what it means for two diseases to be considered similar. A
medical-domain-specific heuristic states that two diseases are similar if
they manifest similar symptoms, and possibly have similar causes. Finding
that the name "Viral-menigitus" is similar to "Bacterial-menigitus"
reinforces the conjecture that they should share similar symptoms.
(Afterall, these two diseases may have been named long before anyone
understood the organisms responsible.) [This "similar name check"
heuristic is also specific to this medical domain.] As we've been told
their respective causes are different, we know to rule out the "similar
causes" conjecture.@FOOT<Of course another MD might only consider two
diseases to be similar if they are caused by the same organism. Such an
expert would be able to enter and use this rule, in leiu of the "similar
diseases have similar symptoms" heuristic discussed above. Of course
this would mean this KA module would have a harder time understanding
this particular (*) analogy.)
Are the two sets of symptoms actually identical? Maybe -- realize we do
not have enough information to determine this yet. We can, however,
simply ask the nearby domain expert.
@FOOT<This question itself might be ill-formed, as we are really comparing
two CLASSes of diseases, not two single diseases. It is quite possible
that one member of each class will share identical symptoms, while other
members of each class will not have such correspondents.>
The fact given in the initial analogy, (*), that these two diseases have
different causes means that their respective etiologies will be
different -- although the similarity of the symptoms places some
constraints on how diverse the etiologies can be. The ontogeny of the
different organisms, likewise, must satisfy some connecting constraints.
[This reasoning will be based on several things. It requires, first, a
basic understanding of some medical "first principles"; here, of the
distinction between bacteria and viruses. In addition, the relation of
cause to etiology must be known, etc.]
Finally, the desired treatments may be completely different -- clearly
antibiotics (which may have some effect on the first bacterial disease)
will be useless for the second viral form. [This again derives from a
combination of general facts about etiology -- that different causes imply
different end results -- and from basic knowledge of these micro-organisms.]
! ---Other Points---
End of the scenario-overview. There are still many second-order issues
which were glossed over, which must be resolved before this process can be
implemented. All of the operations mentioned dealt with slots -- either
determining that a given slot was relevant for a particular unit, or
finding a value for a slot. This is a simplification in two ways. First,
we will really be concerned with general N-ary relations, rather than the
intrinsically binary slots. Second, there will be other operations which
will only place a restriction on the arguments of a proposition, but still
not fully specify these values. (E.g. we may insist that the value of x
in (IsA Analogue2 x) be a member of some set, or that it NOT be some
value, etc.) It is still safe to say that each operation of the
analogizer will attempt to more completely specify some fact about the new
analogue.
The next point deals with the order of those operations -- which
conjectures to propose first, and which later. How, for example, did we
know to first determine Viral-meningitis:IsA? The answer is common sense,
encoded as rule-ordering heuristics. (The "Do IsA first" heuristic is
easy to justify: this "is a particular kind of" relation provides a good
discriminant for subsequent facts; the conjectured value to use is easy to
compute -- i.e. it is usually the same as the IsA of the other analogue;
etc.)
The third "nuance" is a major issue, one which seperates this research
from that of other analogy programs: this program will be able to
"reformulate" the vehicle
@FOOT<This vehicle/topic/ground terminology comes from [Paivio].>
if necessary; and then use THESE newly generated
features for the analogy -- that is, the analogizer will map these
features over to the other analogue. In these cases, the analogizer will
first find a different description of the first analogue, one in which its
relation to the new concept is more apparent. A concluding appendix will
better define this term "reformulation", and provide some examples
justifying why it is needed.
! ---Prerequisite KBs---
As we saw throughout the example above, a lot of knowledge, about various
things, is required to reach these obvious conclusions. We had to employ
facts particular to this medical domain, (including pharmacological facts,
knowledge of infections in general, [e.g. diseases are considered similar
if they exhibit the same "behaviour" (reinforced by naming convention)],)
as well as facts about analogies in general, observations about salience,
etc.. In addition, we needed to include many "common sense" notions --
including a general understanding of causality (e.g. Treatment should be
related to Cause); and a variety of general heuristics -- including the
"Copy IsA, whenever possible, as soon as possible" rule. How to encode
these diverse facts is a major research challenge.
! ---Usefulness---
There are several strong justifications for this work. It will contribute
both to Expert System technology in particular, and to AI in general.
Reasons (1) and (2) below indicate why we feel that this elaborate
automated "copy and edit" process, in and of itself, will facilitate the
construction of superior KBs, faster. (These claims are, of course,
currently just conjectures. They will be empirically tested when this
module is up and running.) This is, however, only the "straight-forward"
component of the a more exciting program(me). Reason (3) discusses our
use of reformulation, which we feel is a contribution to AI in general.
(1) The resultant KB will be more accurate. By automating much of the KA
process, the domain expert is spared the arduous and exacting task of
actually inputting each specific fact about each new object. Not only
will this module help when fleshing out skeletons during the 2nd KA stage,
(see [Bennett: Sacon],) it could also provide a Tieresias-like ([Davis])
verification, to insure that like objects have similar features, with
similar values. (Here the check can exceed Tieresias's purely syntactic
check, using some of its domain knowledge to determine, for example, just
how the values of a given slot for two different units should compare...)
[Actually, this verification would be a (hopefully) straightforward
embellishment to the proposed module.]
(2) The KB will be generated and refined faster.
This is because the language used for the interaction is more accomodating:
a) It is more natural to the expert.
Pf: Consider how experts communicate among themselves -- "this patient
just like that one", or "these chemicals are just like those", or "think
of this as water flow", ...
b) It is more succinct -- relatively few symbols will be used to encode many
assertions.
Pf: Claiming "A is like B" really "expands" into a host of assignments of
facts about A. (Of course storing the declarations which are used to
translate from the statement of the analogy to those assignments may be
non-trivial.)
(3) This module will be able to reformulate the analogues as a first step
in finding the relevant analogy. This may involve simply high-lighting
one particular perspective (or feature-space) of the vechicle, or the more
complex task of deriving a new space of features. (The appendix will
explain this use of reformulation -- telling what we mean by this term,
and why we consider it essential.)
! ---Related (dare I say analogous?) future work---
The ability to comprehend a given analogy, even in these rather
constrained situations, seems a prerequisite for many of the other uses of
analogy. Given a module capable of this behavior, one could imagine
using it to use intERfield connections -- e.g.
"A text editor is like a Secretary, except ...", or
"Computer diagnosis resembles Human diagnosis in that ...",
"An Analog Electrical System is `isomorphic' to a Water Flow Circuit ..."
etc.
The task of finding the best analogue (that is, finding the case which
most resembles some current situation,) would surely use the capability
of understanding how two particular situations are similar, which is just
what this proposed module would provide. (The expert who works from cases,
who examines his 50 - 100K friends (see [Simon]), searching for the one
which is closest to his current case, is using just this ability.)
Consider how one might use analogy for teaching: One has to find to find
the desired analogue-pairs to present, (which is basically the "find best
analogue" task described above,) together with a description of how they
are (and are not) related, which is closely related the KA task discussed
here. The flip-side of teaching, learning, is precisely the KA task.
! ---Conclusion---
This sketch hints at the numerous advantages of using analogy during
Knowledge Acquisition. To make this point (and my thesis) more concrete,
I clearly need is a body of real examples. Trying to be my own Domain
Expert, I originally chose the (more familiar to me) domain of editor
commands as principle domain. This has the major drawback that it is
sufficiently artificial and artifactual that any derived intrafield
analogy felt both obvious and un-interesting.
This is why I would like to work on "deeper" analogies --
perhaps exploring the electrical circuit from water flow (or renal system)
connections.
The following appendices persue this possibility.
Appendix 1 elaborates a major prerequisite of this process, by
posing some of the relevant questions about reformulation.
Appendix 2 then discusses a scenario for how to use the same basic mechanism
which handled the superficial meningitis example above,
augmented as needed to "handle" reformulation, to undertake this EC/WF task.
*********
! ---Appendix 1: More on Reformulation---
Unlike other analogizing programs, this system does NOT depend on one
particular representation for the analogues. It can, instead, select the
most apt perspective, or even generate a new feature space if necessary.
The features the topic will "inherit" will be from that feature-set.
This appendix will answer the questions: Is this reformulation step useful?
If so, why have prior analogizing programs been able to use a single
representation, seemingly able to completely avoid this problem?
One very seductive property of analogies is that any given analogy is
obvious, in retrospect. Once one has described how the analogues A and B
are similar (in general because they are both Ys) any feature which you
find both A and B share will seem obvious -- of course P(x) holds for both A
and B; it holds for all members of Y!
Unfortunately, one does NOT always start with this crisp Y class; instead,
one may be forced to infer it from the examples. This is one of the real
challenges of this work (and its major AI contribution) -- determining how
to glean from the vehicle, together with a brief description of the
desired analogy, the space of relevant facts to map from this analogue
over to the topic.
We need a different example to demonstrate the usefulness of this
reformulation step. (The next appendix will show that major reformulations
are needed to handle the "fairly deep" connection between water flow and
electrical systems. We will persue a slightly easier one here.)
Consider first the obvious connection between blood and lymph --
as each IsA circulating bodily fluid, it is not surprising to
find many correlations. Now imagine that someone said that the endocrine
network is similar to the blood system, except it uses "message carrying"
hormones rather than indistinguishable mass-type blood.
This endocrine system is clearly NOT a circulating bodily fluid. It does,
however, share many properties with such systems. For example, a pathway
may be blocked, preventing transference of the material. Or there maybe
some feedback loops. And, given such a topology, there are a host of
problems which might arise. (E.g. some "Stop Sending" signal might be
lost if the return part of the feedback loop was either open or blocked.)
The reason for these commonalities should be apparent: in both cases some
material is travelling from one location to another. Hence any of the
properties associated with "material flow" should pertain to both of these
systems. But what if the current system lacks this essential category?
We would still want the analogizer to consider endocrine-related illnesses
which resemble blood-blockage, or open-loops. [Sorry I don't know the
names for these ailments.] After analyzing this situation, we may want
to reconfigure the KB to actually have a Material-Flow class, which is a
superset of "circulating bodily fluids", and the class to which "endocrine
system" belongs. Thenafter anything which IsA MaterialFlow would inherit
all of those facts common to such systems -- including this list of
possible illness causes.
(We might later consider connecting our Neurological Networks (or even
electrical curcuits in general) with that endocrine system. They are both
instances of elaborate circuits, and, as such, subject to certain classes
of disruptions.)
As mentioned above, it is only in aftersight that the need for such
categories became obvious -- it is silly to think that we might have
known this, and every other type of relevant category, beforehand.
Solving this challenge -- of how to find such commonalities when they
are needed, especially when they are NOT explicit in the representation,
but rather have to be teased out -- is a major reseach effort.
! ---Appendix 2: More elaborate task---
As a more elaborate example of an analogy, consider how to use
one's knowledge of water circuits to understand electrical circuits.
I feel (and will be testing the hypothesis that) the same mechanism
which was effective for the superficial meningitis analogies mentioned
above can be used for this "deeper" connection.
The following scenarios illustrate the basic process:
<<These particular examples are rather rudimentary, and naive --
having been just concocted today, "on the fly".
We can discuss better correspondences when we meet.>>
(1) Begin with a single Expert System, whose job is to explain
how an analog electrical circuit works -- ala QUAL [deKleer 79].
Our goal is to develop a new ES, which performs the analogous
task of explaining how the renal system operates. That new system
is built during the dialogue which follows the claim that
"(As a water circuit,) the behavior of the renal system is
isomorphic to that of a (corresponding) electrical system,
(as each is an instance of a circuit)." [+]
Relevant questions would include
"What part corresponds to a wire?"
"Is the notion of `resistance' relevant for the Renal system?
If so, what is it's name?"
"Over which type of devices is the `flowing substance' (e.g. water)
conserved?"
(2) Here we begin with have (weak and incomplete versions of) two
Expert Systems, which can explain, respectively, situations which arise
in the domains of analogue electrical circuit and some water flow network
-- e.g. the renal system.
Our goal is to use a statement like [+] above
to improve (i.e. further educate) both systems.
It should also be possible to use this analogical connection to discover
errors of both omission (deficiencies) and comission in each KB.
For example, a naive electrical system, which knows nothing about capacitors,
might inquire if there are such temporary storage units as it
attempts to understand the role of the kidneys. Or an incomplete renal
understanding system might "learn" it has to consider/worry about
the conduits which transport the body's water when it sees the problems
associated with wires. Etc.
Method: Perhaps the correct approach would be to start with a pair of running
systems, like QUAL and Kunz's renal system.
I would then, sequentially, "lobotomize" each of the systems, (leaving the
other one healthy,) and "re-educate" it using an analogy like [+].
The goal would be to derive gallons of the general heuristics --
enough that different tasks (e.g. learning about the endocrine system
based on the message passing formalism of the Actor system) would
"fall out".
One final point: A major concern with any KA system is the worry that
the formalism used to represent the facts might "trivialize" the problem,
by "building in" the answers. Using systems which are already developed,
and designed for performance rather than competence tasks,
somewhat addresses this issue. It also permits me to play with reformulation.
The types of things Kunz will represent will undoubtedly be quite different
from the types of things you chose to describe.
Furthermore, I imagine you two will chose quite different representations
for those things which both systems will encode.
This would be a source of considerable useful data,
to help me determine how to jump from one representation to the other.
-------
< Where did this come from? It had been in ANALOG[rdg,dbl] >
Why am I doing this?
(perhaps with different emphasis)
This work deals with the use of analogy, during the second phase of
Knowledge Acquisition -- (using JSB's three fold scheme).
This section supplies a brief motivation -- why I am looking at
analogy, why analogy as a teaching aide, and why is it being used
for Knowledge Acquisition -- i.e. to input facts into a growing
knowledge base.
Why analogy? The primary reason is my interest in this area: few processes
seem as ubiquitous, or essential, to intelligent thought as the ability
to form and understand analogies.
As I mention in @Cite(NaiveAnalogy),
processes as (at first glance) divergent as understanding language,
formulating new scientific theories, and appreciating music
all seem to require a non-trivial analogizing ability.
Despite the great interest in this phenomenon, from philosophers and
psychologists as well as AIers,
there seems no concensus on how this process operates,
or even on what, exactly, it is.
Why the use of analogy as a teaching tool?
In @Cite(NaiveAnalogy) I list a number of uses of analogy -- ranging from
communication and representation to "discovery". The one I consider most
tractable (and, as I'll explain soon, most testable) is explanation --
where the speaker has an idea to communicate to a competent, if less
knowledgable, hearer. As an (as of yet unverified) research claim,
I feel that the other (more sophisticated?) uses of analogy will all
make heavy use of this "module" -- that is, this particular facility
embodies the "central" (core, primary?) use of analogy,
which the other processes can utilitize and expand.
Why for a KA task?
I have two main reasons:
First, usefulness:
The current central theme in Expert Systems today is KA -- this represents
the major bottle neck impeding the development of these systems.
Corollary 1 claims that, gee, if only we had analogy, this task would
be so much easier...
Second, testability:
Hooking the results of an analogical derivation to an existing, running
expert system renders those results ?easy to test? -- the improved system
either gives meaningful results, over this new (sub)domain or it doesn't.
(Still leaves open a few issues -- like whether it cheated or not, and
whether it was really using analogy or not...)
What do I hope to accomplish? First, some relevant, (scholarly?)
inter-disciplinary research on this <ubiquitous> issue of analogy --
one which sheds some light on this unfortunately sloppily pursued
area. Second, a running program which may be usable by other researchers
for their projects. Third, a clearer understanding, in my mind at least,
of some of the underlying processes which are going on in our heads
during "intelligent" activities, as manifest by our frequent, and easy
use, of this complex reasoning process, analogy.
∂16:08 2-May: lenat@score/su Sketch of Thesis Overview
Doug -
Here is a QUICK sketch of my ideas -- loose enough for much revision,
but better than a blank sheet.
Russ
-------********-------********-------********-------
[Level 0]
My thesis will have two parts:
I. A theoretic perspective, describing
what an analogy is
what a good analogy is
how my program(me) fits into that space
II. (A description of) My running program
which uses analogy for the task of knowledge acquisition
----
[Level 1]
Towards defining what an analogy is:
A] Analogy connects 2 objects, NOT their representations.
[Hence reformulation is important part]
B] Needs context/perspective/task-description
C] Use "siblings-in-abstraction-space" view of analogy
Instantiation after reformulation
[[reformulation may be nil]]
To determine what a GOOD analogy is:
A] depends heavily on task/goal
B] very subjective -- different users will want different ones.
Focus of my program:
A] Analogy as a mechanism for learning
-- after hearing that A is like B, conjecturing new facts re A.
-- two analogues: topic and vehicle, using ground (= common abstraction)
where ground may have to be constructed.
-- at "instance - instance" level [not model/instance or prototype/instance]
B] Other properties
i) Interactive
(so can conjecture, then receive confirmation)
ii) Unidirectional
(so will not help to understand B)
iii) at an instant
(so learning new facts re: B will not carry over)
******
Approach to Construction of Program [#II. above]
I: Select a pair of domains which are
(1) known to be analogous
(2) which have existant "expert systems" implemented
II: Build analogizer,
(1) capable of taking facts from one domain to other.
(2) "Input"
Access to KB for each domain
[Includes "performance" level facts, and "competence" first principles]
(User-modifiable) corpus of "Analogizing Heuristics"
(User provided) analogy statements
(3) "Output"
Modification to a KB
[User interaction -- to answer questions]
(4) internal structure [see (2) above]
Simple inference engine
[possibly geared to analogizing rules]
Crude Interface to users, into engine
Some general domain-independent analogizing rules
Some specific analogizing rules
III: Configure system
(1) Find KBs for these domains, in correct format
(2) (Hand) Generate domain specific rules
IV: (Attempt to) run analogies
(1) Scenario:
User suggests analogy
Interaction as Analogizer clarifies analogy desired
KB is modified
(2) Notice other analogies during above process,
add these to Analogizing rules
(in as general a form as possible)
(3) Process trivial ones, (those w/obvious answers,) first
Then progress to more difficult (encompassing) ones
*****
Current state:
I: I chose water flow and electricity, for reasons above.
[Hoping to use deKleer's and Kunz's programs]
[Later maybe intelligent agents and endocrines, or oil spill, ...]
II: Hand done -- still much tweaking to do.
III: Am now working here -- trying to get KBs of domains.
To get KB for electricity:
Hoped to adapt deKleer's system.
Needed to show him what type of facts I wanted,
so am now constructing simple fluid flow "ES-ette".
To get KB for water flow -
will talk to John Kunz, about his MRS based Renal failure ...
Note that I am now getting a sense of some aspects, by this finger
exercise (of building fluid example)
EG (omission in deKleer) All pipes are assumed full.
(I think Kunz has non-at-capacity connections...)
//Named WC - for water circuit. Maybe will later "Reiger" it by modelling
a water closet...//
Future: finish everything being done now.
Do part I of thesis... once system is "turning over".
-----
Pipes in circuit
in Unix
For MRG's ONL proposal: [Never used]
<<KA is important>>
The major focus of Expert System work
{currently} | {in this 1980 decade}
is "Knowledge Acquisition" (KA) process [Feigenbaum??].
This is the process of adding the knowledge a human expert has
(in the form of facts, heuristics, insights, etc.)
to a growing KB.
This task has proven to be more difficult than originally thought,
and is the major bottleneck in ES technology today.
One reason is that the expert would have
{? to accomodate the computer rather than vice versa. ?}
to express his knowledge in the KE's language,
which he would often find not just difficult and time consuming,
but quite awkward and unnatural.
<<Analogy is a tool for doing this>>
Many programs have been written to facilitate this knowledge transference.
[BES, AGE, EMYCIN, ... ?SACON?, ROGET, ...]
Our approach is to make the interface a little more natural,
by allowing the expert to communicate using analogies.
Hence, rather than state that
"Viral meningitis is a disease, whose symptoms include ..., and ..."
he could simply indicate that
"Viral meningitis is like bacterial meningitis, except it is
caused by a virus".*
[*Foot: We use English phrases here for illustrative purposes --
we are NOT building a Natural Language interface.]
We are working on providing the expert with an addition tool,
The "Analogizer" would use this second statement to deduce the many of
the facts included by the first, possibly subject to the user's confirmation.
We view the analogy as a laconic way of communicating a body of facts,
transfered onto the topic from the vehicle.
Greiner's thesis work
My approach involves a "forcing function" -- trying to solve a particular
problem, and using this to guide (build) an understanding of some new
domain, or part of a domain.
For example, from an understanding of electricity, try to learn more about
water flow, to solve some particular problem (e.g. the pressure at some
point).
Have to generate an "umbilical cord", a mapping which leads from the known
"parent" domain to the neonatal "child" domain; and then exploit this,
to conjecture new facts re: the new domain.
Then interaction will lead to correct (from reasonable) mapping.
(Later will have set of queries, thru which misc facets of domain can be
addressed.)
Other work -- usually unbounded, and non-interactive.
Also, some work here on reformulation
.....
While KEs have made important progress in
many of the issues associated with Expert System,
the task of creating and updating a KB -- called Knowledge Acquisition --
is still in its infancy.
-----
new terms -- intensional descriptions (not just for reformulation)
∂15-Sep-83 1800 greiner@Diablo Thesis overview
To: genesereth@sumex, lenat@sumex, buchanan@sumex
Cc: rdg@sail
Message-Id: <83/09/15 1652.783@Diablo>
Gentlemen,
Following Bruce's recent (excellent) suggestion, I prepared a thumb-nail
sketch of what I'm doing -- including especially what I hope to prove,
and how. A draft of that document follows. Your comments are eagerly
encouraged.
Thanks you,
Russ
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
On "The Use of Analogy for Knowledge Acquisition"
Objectives of Russell Greiner's thesis work
[Scenario, Behavior, Process, New ideas/Contributions, Hypotheses/Validation]
*** Scenario ***
Problem solver S is unable to solve problem P in domain X. Expert E then
tells S that "X is like Y", (possibly augmented with a "within constraint C"
clause). S's analogizer, A, uses this to propose an answer, R, to this
problem, based on a mapping, m, from Y to X. [That mapping will be defined
more precisely below.] If E accepts R (and m) as correct, (or is willing to
provide some minor corrections to m's result), those newly deduced facts
will be added to ThX. Otherwise, A will try again.
-------
*** Behavior ***
Input:
* ThY - description of Y (e.g. electricity)
* ThX - partial description of X (e.g. water-systems)
* P - problem to solve, dealing with domain X (in language of X)
-- e.g. (pressure j-c $x)
( * ThG - general facts about the world, independent of X and Y )
Stored Information:
* miscellaneous known abstractions and perspectives
[possibly based-on/justified-by previous solved problems]
* library of domain-independent, analogizing heuristics
...
Output (after each iteration):
* R - a proposed solution to P
* m - a mapping from Clauses(Ly) to Clauses(Lx)
where Ly is the language of ThY, and Lx, of ThX.
(Technically the domain of the mapping will be Clauses(La),
where La is the langauge of the abstraction ThA.
However, in general La < Ly.)
* m(ThY) - new facts, to add into ThX
[Note that both A and m(ThY) can be deduced from m;
and a clause is either a term or a proposition.]
Notes:
* There may be many iterations,
each generating a mapping (and associated proposed solution).
These mappings will be generated in a "best-first" order, based on
analogy-ordering heuristics.
* This process may be interactive, with the analogizer asking questions
(usually Yes/No) of the expert.
* The overall analogizing system may "learn":
As a side-effect of the analogizing process
(many new bits of information may be added to the system)
- the theory of X will be expanded
- new abstractions/perspectives may be noted/incorporated
* Multiple partial analogies fit nicely into this framework:
To understand X, the expert may first use the "X is like Y1" analogy, then
some different "X is like Y2", followed "X is like Y3", etc., where each is
used to solve a different problem, and thereby point out distinct aspects
of the full domain X.
!-------
*** Process ***
This model of analogizing has several conceptual steps:
(1) determine (select or build) some abstraction of Y, ThA;
(2) generate new sentences to add to ThX, each corresponding to
some sentence in ThA;
(3) "verify" this augmented ThX:
Does it provide a solution to P?
If so, does E approve it?
.....
Part (1), determining the best abstraction,
will require all of the inputs: P, ThX and ThY.
[How? This is still a major research topic.]
The major work of the second part of the analogizer is the (incremental)
construction of the mapping m, which will be used to produce the proposed
new domain-X facts. The constraints on this mapping are stated in terms of
the new facts in produces, m(ThA): These sentences must be consistent with
those already in ThX+ThG, and they must provide a solution to P.
The first constraint provides a useful, early pruner: uas consistency is
monotonic in the facts of a theory, any partial mapping which leads to an
inconsistent theory can be pruned away, along with all of its extension.
The second constraint both leads to useful heuristics to help generate the
mapping, and provides the "termination" test of the second phase of the
analogizer (written above as step (3).)]
-------
*** New ideas/Contributions ***
(1) Use of abstraction/perspective to constrain the space
[by restricting the domain to Clauses(La),
which is usually << Clauses(Ly).]
(2) Consistency -- the analogically-deduced new facts must be consistent.
[this helps both to guide the generation of the map,
and to prune unfeasible candidate, early.]
(3) Relevancy -- result of analogical must provide some solution to P.
- focus on the useful, "reasonable" analogies
- helps guide the generation of the analogy-map
(4) ? Feedback -- each incremental addition to the mapping is motivated by
"what seems to be needed"
* Formal definition of (space of) analogies
[viz: an analogy is based on a 1:1 partial mapping, taking Clauses(Ly)
into Clauses(Lx), whose sentence-to-sentence extension leads
to a consistent theory which provides an answer to the problem.]
* Improved understanding (and use) of "abstraction"
* (Demonstrates) an actual use of analogy!
- within a general, domain-independent framwork
- useful in "widening" a real problem: the KA bottleneck
!-------
*** Hypotheses/Validation ***
0. Analogizer will produces "interesting and often correct" results.
Interesting to: RDG (+ reading committee?)
Unfortunately:
- NO massive psychology test will be performed.
However:
- may match it to known results - see Carbonell, SA Douglas, Anderson
1. Features (1)-(4) above are sufficient to produce "reasonable" analogies.
("Reasonable" to the expert.)
Unfortunately:
- NO guarantee that it will always
"eventually generate the *correct* answer".
Analogy is too weak a method;
the correct answer will occasionally NOT be in the space.
However:
- Analogizer will always be able to "justify" why its answer
is reasonable.
2. This Analogizer is useful tool:
Test:
Compare the KA process with and without this analogizer, asking if
the expert can add facts
faster
with fewer keystrokes
more naturally
? more accurately ?
with this analogizer (vs without this tool).
[Again, NOT a massive test -- just on a few samples.]
3. It is essential for an Analogizer to "focus" on a particular problem
(see (3) above),
as the analogizer will often generate "silly" results otherwise.
Test:
Take out constraint (3) above, and see if system
- generates many silly results,
- takes longer to generate anything meaningful,
(as predicted).
(The early pruning of inconsistent map extensions will OBVIOUSLY help --
no need to test that.)
←←←←←←←←←←←←←
-------------
Suggested by BGB 14/Sept/83
Iteration 1: 15/Sept/83 [to MRG, DBL, BGB]
Iteration 2: will also include L. Darden, J. deKleer, P. Hart, B. Clancey
J. Carbonell, P. Winston, Burnstein@Yale,
Mitchell, Keller, ... @Rutgers
∂16-Sep-83 0644 BUCHANAN@SUMEX-AIM Re: Thesis overview
To: greiner@Diablo@Score
cc: genesereth@SUMEX-AIM, lenat@SUMEX-AIM, rdg@SAIL, buchanan@SUMEX-AIM
In-Reply-To: Your message of Thu 15 Sep 83 16:52:00-PDT
Russ,
I still think that the hypothesis and the demonstration methods need
to be firmed up -- probably before iterating over a wider audience.
Ideas (1)-(4) are ok as one-liners, but we also have to work to add
some substance behind them. The question of HOW all this works can't
be put off, but may require some coding to experiment with the ideas.
This is a very good outline. I understand what you're up to better
than I ever have.
I would feel better if you were choosing domains of interest to someone.
Physics is pretty well understood and we do not have any systems that
require new knowledge of water flow.
bgb
-------
∂11:14 19-Sep: BUCHANAN@SUMEX-AIM/su Re: "Re: Thesis overview"
Bruce -
Thanks for your quick comments on my thesis proposal outline.
I have several responses/questions -- would you prefer discussing them
via messages, or face-to-face? If the latter, when would be a good time
for you?
Russ
∂RDG-
I'll apply it to other domains as well.
Eg: MRG's initial interest in this area was to understand the
body's water systems (as in Kunz' system)
∂16:42 21-Sep: BUCHANAN@SUMEX/su Thesis meeting
The purpose of this note is to schedule a quick meeting,
to take place before your upcoming trip.
Time:
My schedule is pretty open -- the only known clutters are the
orientation get-togethers, (this week), and a weekly meeting with MRG
at 3:30 on Fridays; and TW's course Wednesday afternoons (2:15-?).
(Weekends are always good too.)
Topics:
* How to "firm up" the hypothesis and the demonstration methods.
[Especially as this must be done before coding the system.]
* I can report on progress wrt ideas (1)-(4).
* Response to your "bad domain" challenge
----
Russ
∂11:05 14-Sep: hart@sri-kl/su Events, past and future
Peter -
A delayed "Welcome back from the East", and "Happy New Year"
(both of which I assume are appropriate...)
How are things in SynTelligence?
Did the fellow I met in IJCAI contact you? Still dancing?
My analogy stuff is progressing, I (? deceive myself to ?) think in
a positive direction. (If your hecticity index is low enough,)
I'd love to get your comments on my approach and preliminary results.
Lynne sends her greetings, of course.
Russ
∂16:56 19-Sept: hart@sri-kl/su Sketch of thesis objective
Peter -
Read this ONLY if you have a few minutes (and a slightly
mascochistic bent) -- if you don't get a chance, I'll be pleased
to go over it tomorrow, real time.
See you Tuesday, at 5:30,
Russ
-------
<<proposal>>
∂20-Sep-83 1044 HART@SRI-KL.ARPA Re: Sketch of thesis objective
Russ,
I merely skimmed your thinkpiece, so most 2ill have to wait until
this pm. However, one phrase stuck inmy mind, partly beause it occurs in
many dialogs; i.e., "the KA bottleneck." I'm coming to the view that the
KA bottleneck is no different from "the software bottleneck" (a.k.a "the
programming bottleneck," etc). That is, knowledge acquisition is essentially
programming in a high-level, non-procedural language, and we should expect
all the problems of "software in sgeneral" to occur in KA for expert systems.
I know that this little tirade doesn't have anything to do with
your thesis proposal substantively, but was curious to see if you have any
reaction to this as a point of view.
See you late pm today,
Peter
-------